// https://leetcode.cn/problems/final-prices-with-a-special-discount-in-a-shop/
// Created by ade on 2022/9/1.
// 具体的，我们可以从前往后处理所有的 nums[i]，使用某类容器装载我们所有的「待打折」的商品下标。假设当前处理到的是 nums[i]：
//
//若其比容器内的任意商品价格要高，其必然不能更新任何一个待打折商品的价格，将其也加入容器尾部（此时我们发现，若有一个新的商品加入容器，其必然是当前所有待打折商品中的价格最高的，即容器内的商品价格单调递增）；
//若其价格不高于容器内的商品价格，其能够更新容器内待打折的商品价格，并且由于我们容器满足单调递增特性，我们必然能够从尾部开始取出待打折商品来进行更新，直到处理完成或遇到第一个无法更新价格的商品。
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

class Solution {
public:
    // 1.直接两个for循环可以

    // 2.单调栈
    vector<int> finalPrices(vector<int> &prices) {
        stack<int> st;
        for (int i = prices.size() - 1; i >= 0; i--) {
            while (!st.empty() && st.top() > prices[i]) {
                st.pop();
            }
            int tmp = prices[i];
            if (!st.empty()) {
                prices[i] -= st.top();
            }
            st.push(tmp);
        }
        return prices;
    }
};

int main() {
    Solution so;
    vector<int> nums = {8, 4, 6, 2, 3};
    auto a = so.finalPrices(nums);
    for (auto i : a) {
        cout << i << ",";
    }
    cout << endl;
    return 0;
}
